package com.common;

import com.merge.pojo.Data;

/**
 * 最小堆
 */
public class MinHeap {

    //堆的容量
    private int capacity;

    //存放的数据（二叉树结构）
    private Data[] data;

    private MinHeap(Data[] data) {
        this(data, data.length);
    }

    private MinHeap(Data[] data, int capacity) {
        if (ArrayUtils.empty(data))return;
        this.capacity = capacity;
        this.data = data;
    }

    public boolean empty() {
        if (capacity == 0) return true;
        return false;
    }

    /**
     * 获取最小值
     * @return
     */
    public Data getMinValue() {
        if (capacity <= 0) return null;
        //数组第一个就是最小值
        Data value = data[0];
        data[0] = data[capacity - 1];
        capacity--;
        downAdjust(data, 0, capacity);
        return value;
    }

    public boolean addValue(Data value) {
        if (capacity >= data.length) {
            System.out.println("minheap容量已满");
            return false;
        }
        data[capacity++] = value;
        upAdjust(data, capacity - 1, capacity);
        return true;
    }

    /**
     * 构建最小堆结构
     */
    public static MinHeap construct(Data[] data) {
        return construct(data, data.length);
    }


    /**
     * 构建最小堆结构
     */
    public static MinHeap construct(Data[] data, int capacity) {
        /*
            获取最后一个非叶子结点的下标（最后一个叶子结点的父节点）
        */
        int index = (capacity - 1) / 2;
        //从最后一个非叶子结点开始，依次下浮
        for (int i = index; i >= 0; i--) {
            downAdjust(data, i, capacity);
        }
        return new MinHeap(data, capacity);
    }

    /**
     *下浮调整
     * @param data
     * @param index
     */
    public static void downAdjust(Data[] data, int index, int capacity) {
        //非叶子点
        while (!leaf(data, index, capacity)) {
            int swapChildIndex = index * 2 + 1;
            if (swapChildIndex + 1 < capacity && data[swapChildIndex].getValue() > data[swapChildIndex + 1].getValue()) {
                swapChildIndex++;
            }
            if (data[index].getValue() < data[swapChildIndex].getValue()) break;
            ArrayUtils.swap(data, index, swapChildIndex);
            index = swapChildIndex;
        }
    }

    /**
     * 向上调整
     * @param data
     * @param index
     * @param capacity
     */
    public static void upAdjust(Data[] data, int index, int capacity) {
        if (index > capacity - 1) return;
        int parentIndex = index / 2;
        while (index > 0 && data[index].getValue() < data[parentIndex].getValue()) {
            ArrayUtils.swap(data, index, parentIndex);
            index = parentIndex;
            parentIndex = index / 2;
        }
    }

    /**
     * 是否为叶子结点
     * @param data
     * @param index
     * @return
     */
    public static boolean leaf(Data[] data, int index, int capacity) {
        int leftChildIndex = index * 2 + 1;
        if (leftChildIndex < capacity) return false;
        return true;
    }

    /**
     * 获取完全二叉树的高度
     * @param data
     * @return
     */
    public static int heigh(Data[] data) {
        int length = data.length;
        int heigh = 1;
        int sum = 0;
        while ((sum += Math.pow(2, heigh-1)) < length) {
            heigh++;
        }
        return heigh;
    }

    public  void print() {
        print(data);
    }

    public void print(Data[] data) {
        int height = heigh(data);
        int count = 0;
        int depth = 1;
        for (int i = 0; i < capacity; i++) {
            for (int j = height - depth; j >= 1; j--) {
                System.out.print("\t");
            }
            System.out.print(data[i].getValue());
            System.out.print("\t");
            if (++count == Math.pow(2, depth - 1)) {
                count = 0;
                depth++;
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        Data[] data = new Data[10];
        for (int i = 1; i <= 9; i++) {
            data[i - 1] = new Data(i, "slice_queue");
        }
        MinHeap minHeap = construct(data, 9);
        minHeap.print();
        System.out.println();
        Data value = new Data(0, "slice_queue");
        minHeap.addValue(value);
        minHeap.print();

    }
}
